package labuladong.第四章;

import leetcode.Head;
import leetcode.ListNode;

/**
 * 回文列表
 */
public class PalidList {
    static ListNode left;

    public static void main(String[] args) {
        ListNode head = Head.genListPalidEven();
        System.out.println(isPalindrome1(head));
        System.out.println(isPalindrome2(head));
    }

    /**
     * 第一种
     * @param head
     * @return
     */
    public static boolean isPalindrome1(ListNode head) {
        left = head;
        return traverse(head);
    }

    public static boolean traverse(ListNode right) {
        if(right == null) {
            return true;
        }
        boolean res = traverse(right.next);
        res = res && (right.val == left.val);
        left = left.next;
        return res;
    }

    /**
     * 第二种
     * @param head
     * @return
     */
    public static boolean isPalindrome2(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (slow != null && fast != null && fast.next != null ) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 如果fast指针没有指向null，说明链表长度为奇数，slow要再向前一步，否则为偶数
        if(fast != null) {
            slow = slow.next;
        }
        ListNode left = head;
        ListNode right = reverse(slow);
        while (right != null) {
            if(right.val != left.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }

    public static ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = head;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
